import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * 判断一个树是不是完全二叉树
 * User: xwl
 * Date: 2023-05-22
 * Time: 22:17
 */

// 节点类
class TreeNode2 {
    int val;
    TreeNode2 left;
    TreeNode2 right;
    TreeNode2() {}
    TreeNode2(int val) { this.val = val; }
    TreeNode2(int val, TreeNode2 left, TreeNode2 right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Test2 {

    /**
     * 判断是否是完全二叉树
     * @param root:树的根节点
     * @return
     */
    public boolean isCompleteTree(TreeNode2 root) {
        // 讨论树为空的情况
        if (root == null) {
            return true;
        }
        // 创建一个队列用来存放树的节点的值
        Queue<TreeNode2> queue = new LinkedList<>();
        queue.offer(root);
        // 入队
        while (!queue.isEmpty()) {
            TreeNode2 cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        // 出队并判断
        while (!queue.isEmpty()) {
            TreeNode2 tmp = queue.poll();
            if (tmp != null) {
                return false;
            }
        }
        // 返回
        return true;
    }

}
